{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Value of an Ordered Triplet II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumTripletValue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有序三元组中的最大值 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>nums</code> 。</p>\n",
    "\n",
    "<p>请你从所有满足&nbsp;<code>i &lt; j &lt; k</code> 的下标三元组 <code>(i, j, k)</code> 中，找出并返回下标三元组的最大值。如果所有满足条件的三元组的值都是负数，则返回 <code>0</code> 。</p>\n",
    "\n",
    "<p><strong>下标三元组</strong> <code>(i, j, k)</code> 的值等于 <code>(nums[i] - nums[j]) * nums[k]</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [12,6,1,2,7]\n",
    "<strong>输出：</strong>77\n",
    "<strong>解释：</strong>下标三元组 (0, 2, 4) 的值是 (nums[0] - nums[2]) * nums[4] = 77 。\n",
    "可以证明不存在值大于 77 的有序下标三元组。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,10,3,4,19]\n",
    "<strong>输出：</strong>133\n",
    "<strong>解释：</strong>下标三元组 (1, 2, 4) 的值是 (nums[1] - nums[2]) * nums[4] = 133 。\n",
    "可以证明不存在值大于 133 的有序下标三元组。 \n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>唯一的下标三元组 (0, 1, 2) 的值是一个负数，(nums[0] - nums[1]) * nums[2] = -3 。因此，答案是 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-value-of-an-ordered-triplet-ii](https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-value-of-an-ordered-triplet-ii](https://leetcode.cn/problems/maximum-value-of-an-ordered-triplet-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[12,6,1,2,7]', '[1,10,3,4,19]', '[1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTripletValue(self, nums: List[int]) -> int:\n",
    "        max_since: list[int] = [0] * len(nums)\n",
    "        max_since[-1] = nums[-1]\n",
    "        for i in range(len(nums) - 2, -1, -1):\n",
    "            max_since[i] = max(nums[i], max_since[i + 1])\n",
    "\n",
    "        max_triplet: int = 0\n",
    "        for i in range(len(nums) - 2):\n",
    "            for j in range(i + 1, len(nums) - 1):\n",
    "                triplet: int = (nums[i] - nums[j]) * max_since[j + 1]\n",
    "                max_triplet = max(max_triplet, (nums[i] - nums[j]) * max_since[j + 1])\n",
    "\n",
    "        return max_triplet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTripletValue(self, nums: List[int]) -> int:\n",
    "        result, maxDiff, preMax=0,0,0\n",
    "        for x in nums:\n",
    "            result=max(result,maxDiff*x)\n",
    "            maxDiff=max(maxDiff,preMax-x)\n",
    "            preMax=max(preMax,x)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTripletValue(self, nums: List[int]) -> int:\n",
    "\n",
    "        res = 0\n",
    "        for i in range(len(nums) - 2):\n",
    "            diff_max = 0\n",
    "            for j in range(i + 1, len(nums) - 1):\n",
    "                if nums[i] < nums[j]:\n",
    "                    continue\n",
    "                diff_max = max(diff_max, nums[i] - nums[j])\n",
    "                kmax = 0\n",
    "                for k in range(j + 1, len(nums)):\n",
    "                    kmax = max(nums[k], kmax)\n",
    "                    res = max(diff_max * kmax, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTripletValue(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "    Function to find the maximum value of (nums[i] - nums[j]) * nums[k] for i < j < k\n",
    "    \"\"\"\n",
    "        max_val = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        for j in range(1, n-1):\n",
    "            max_i = max(nums[:j]) # Max value in nums[0] to nums[j-1]\n",
    "            max_k = max(nums[j+1:]) # Max value in nums[j+1] to nums[n-1]\n",
    "\n",
    "            # If there are elements both before and after j\n",
    "            if j > 0 and j < n-1:\n",
    "                max_val = max(max_val, (max_i - nums[j]) * max_k)\n",
    "\n",
    "        return max_val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTripletValue(self, nums: List[int]) -> int:\n",
    "        prev_max = 0\n",
    "        prev_max_diff = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i > 1:\n",
    "                ans = max(ans, nums[i] * prev_max_diff)\n",
    "            if i > 0:\n",
    "                prev_max_diff = max(prev_max_diff, prev_max - nums[i])\n",
    "            \n",
    "            prev_max = max(prev_max, nums[i])\n",
    "            \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTripletValue(self, nums: List[int]) -> int:\n",
    "        ans = max_diff = pre_max = 0\n",
    "        for x in nums:\n",
    "            ans = max(ans, max_diff * x)\n",
    "            max_diff = max(max_diff, pre_max - x)\n",
    "            pre_max = max(pre_max, x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTripletValue(self, nums: List[int]) -> int:\n",
    "        maxDiff = minDiff = nums[0] - nums[1]\n",
    "        maxNum, minNum = (nums[0], nums[1]) if maxDiff > 0 else (nums[1], nums[0])\n",
    "        ans = 0\n",
    "        for k in range(2, len(nums)):\n",
    "            new_ans = nums[k] * maxDiff if nums[k] > 0 else minDiff\n",
    "            ans = max(ans, new_ans)\n",
    "            maxDiff = max(maxDiff, maxNum - nums[k])\n",
    "            minDiff = min(minDiff, minNum - nums[k])\n",
    "            maxNum = max(maxNum, nums[k])\n",
    "            minNum = min(minNum, nums[k])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTripletValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        preMax = 0\n",
    "        maxDiff = 0\n",
    "        res = 0\n",
    "        for num in nums:\n",
    "            res = max(res, maxDiff * num)\n",
    "            preMax = max(preMax, num)\n",
    "            maxDiff = max(maxDiff, preMax - num)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTripletValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [ -1 ] * n\n",
    "        dp1 = [ -1 ] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dp[i] = max(dp[i+1], nums[i+1]) if i != n - 1 else -1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            dp1[i] = max(dp1[i-1], nums[i-1])\n",
    "            if i != n - 1:\n",
    "                ans = max(ans, (dp1[i] - nums[i]) * dp[i])\n",
    "        \n",
    "        return ans if ans > 0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTripletValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        arr1 = [0]*n\n",
    "        arr2 = [0]*n\n",
    "        t = -inf\n",
    "        for i in range(n):\n",
    "            arr1[i] = max(t,nums[i])\n",
    "            t = max(t,nums[i])\n",
    "        t = -inf\n",
    "        for i in range(1,n):\n",
    "            arr2[i] = max(t,arr1[i-1]-nums[i])\n",
    "            t = max(t,arr1[i-1]-nums[i])\n",
    "        ans = 0\n",
    "        for k in range(2,n):\n",
    "            ans = max(ans,nums[k]*(arr2[k-1]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTripletValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [ -1 ] * n\n",
    "        dp1 = [ -1 ] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            dp[i] = max(dp[i+1], nums[i+1]) if i != n - 1 else -1\n",
    "        \n",
    "        for i in range(n):\n",
    "            dp1[i] = max(dp1[i-1], nums[i-1]) if i >= 1 else -1\n",
    "        \n",
    "        print(dp, dp1)\n",
    "        ans = 0\n",
    "        for i in range(1, n-1):\n",
    "            ans = max(ans, (dp1[i] - nums[i]) * dp[i])\n",
    "        \n",
    "        return ans if ans > 0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maximumTripletValue(self, nums: List[int]) -> int:\n",
    "#         ans = max_diff = pre_max = 0\n",
    "#         for x in nums:\n",
    "#             ans = max(ans, max_diff * x)\n",
    "#             max_diff = max(max_diff, pre_max - x)\n",
    "#             pre_max = max(pre_max, x)\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def maximumTripletValue(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        suf_max = [0] * (n + 1)\n",
    "        for i in range(n - 1, 1, -1):\n",
    "            suf_max[i] = max(suf_max[i + 1], nums[i])\n",
    "        ans = pre_max = 0\n",
    "        for j, x in enumerate(nums):\n",
    "            ans = max(ans, (pre_max - x) * suf_max[j + 1])\n",
    "            pre_max = max(pre_max, x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTripletValue(self, nums: List[int]) -> int:\n",
    "        # 前后缀\n",
    "        n = len(nums)\n",
    "        suf = [0] * (n + 1)\n",
    "        for i in range(n-1, -1, -1):\n",
    "            suf[i] = nums[i] if nums[i] > suf[i+1] else suf[i+1]\n",
    "        \n",
    "        pre = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            pre[i] = nums[i] if i == 0 or nums[i] > pre[i-1] else pre[i-1]\n",
    "            \n",
    "        res = 0\n",
    "        for i in range(1, n-1):\n",
    "            res = max(res, (pre[i-1] - nums[i]) * suf[i+1])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTripletValue(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        pre = [float(\"-inf\")]\n",
    "        for i in nums[::-1]:\n",
    "            pre.append(max(pre[-1], i))\n",
    "        s = float(\"-inf\")\n",
    "        for i in nums[:-1]:\n",
    "            pre.pop()\n",
    "            res = max(res, (s - i) * pre[-1])\n",
    "            s = max(s, i)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumTripletValue(self, nums: List[int]) -> int:\n",
    "        N = len(nums)\n",
    "        f = [ float(\"inf\") for _ in range(N) ]\n",
    "        f[0] = 0\n",
    "        p = [ 0 for _ in range(N) ]\n",
    "        p[N-1] = 0\n",
    "        ans = 0\n",
    "        for i in range(1, N):\n",
    "            f[i] = max(f[i-1], nums[i-1])\n",
    "        for j in range(N-2, -1, -1):\n",
    "            p[j] = max(p[j+1], nums[j+1])\n",
    "            ans = max(ans, (f[j] - nums[j]) * p[j])\n",
    "        # print(f, p)\n",
    "        return ans\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
